home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / 2DLab / voronoi.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-01-14  |  4.3 KB  |  181 lines
  1. #include "headers.h"
  2.  
  3. int triangulate = FALSE, sorted, plot, debug = FALSE, randmode, outputmode;
  4. float xmin, xmax, ymin, ymax, deltax, deltay;
  5.  
  6. char execdir[80];
  7.  
  8. struct Site _sites[MAXSITES], *sites = _sites;
  9.  
  10. int nsites;
  11. int siteidx;
  12. int sqrt_nsites;
  13. int nvertices;
  14. struct Freelist sfl;
  15. struct Site *bottomsite;
  16.  
  17. int nedges;
  18. struct    Freelist efl;
  19.  
  20. struct Freelist    hfl;
  21. struct Halfedge *ELleftend, *ELrightend;
  22. int ELhashsize;
  23. struct Halfedge **ELhash;
  24.  
  25. int PQhashsize;
  26. struct Halfedge *PQhash;
  27. int PQcount;
  28. int PQmin;
  29.  
  30. /* sort sites on y, then x, coord */
  31. int scomp(s1,s2)
  32. struct Point *s1,*s2;
  33. {
  34.     if(s1->y < s2->y) return(-1);
  35.     if(s1->y > s2->y) return(1);
  36.     if(s1->x < s2->x) return(-1);
  37.     if(s1->x > s2->x) return(1);
  38.     return(0);
  39. }
  40.  
  41. /* sort GLsites on y, then x, coord */
  42. int GLscomp(s1,s2)
  43. VERT *s1,*s2;
  44. {
  45.     if(s1->y < s2->y) return(-1);
  46.     if(s1->y > s2->y) return(1);
  47.     if(s1->x < s2->x) return(-1);
  48.     if(s1->x > s2->x) return(1);
  49.     return(0);
  50. }
  51.  
  52. /* return a single in-storage site */
  53. struct Site *
  54. nextone()
  55. {
  56.     if(siteidx < nsites)
  57.     return (&sites[siteidx++]);
  58.     else
  59.     return( (struct Site *)NULL);
  60. }
  61.  
  62. sortGLsites()
  63. {
  64. int k;
  65. float randr(), dx, dy;
  66.  
  67.     qsort((char *)GLsites, nsites, sizeof (VERT), GLscomp);
  68.  
  69.     /* check: are there coincident points? */
  70.     for (k = 1; k < nsites; k++)
  71.     if ((GLsites[k-1].y == GLsites[k].y) && (GLsites[k-1].x == GLsites[k].x))   {
  72. /*        printf ("coincident sites at %d, %d!\n", k-1, k);*/
  73.         dx = GLsites[k].x * (1.0 / 4096.0);
  74.         dy = GLsites[k].y * (1.0 / 4096.0);
  75.         /* hack: jitter the last point randomly in its last significant digit */
  76.         GLsites[k-1].x += randr (-dx, dx);
  77.         GLsites[k-1].y += randr (-dy, dy);
  78.         }
  79. }
  80.  
  81. /* implicit parameters: nsites, sqrt_nsites, xmin, xmax, ymin, ymax,
  82.    deltax, deltay (can all be estimates).
  83.    Performance suffers if they are wrong; better to make nsites,
  84.    deltax, and deltay too big than too small.  (?) */
  85. voronoi (nextsite)
  86. struct Site *(*nextsite)();
  87. {
  88. struct Site *newsite, *bot, *top, *temp, *p;
  89. struct Site *v;
  90. struct Point newintstar;
  91. int pm;
  92. struct Halfedge *lbnd, *rbnd, *llbnd, *rrbnd, *bisector;
  93. struct Edge *e;
  94.  
  95.     myfreeall ();
  96.  
  97.     if (nsites <= 1)
  98.     return;
  99.  
  100.     freeinit(&sfl, sizeof (struct Site));
  101.  
  102.     /* bboxinit();   /* copies static array into nsites */
  103.     geominit();        /* internal use of deltax, deltay  */
  104.  
  105.     PQinitialize();
  106.     bottomsite = (*nextsite)();
  107.     out_site(bottomsite);
  108.     ELinitialize();
  109.  
  110.     newsite = (*nextsite)();
  111.     while(1) {
  112.     if(!PQempty()) newintstar = PQ_min();
  113. /* new site is smallest */
  114.     if (newsite != (struct Site *)NULL && (PQempty() 
  115.          || newsite->coord.y < newintstar.y
  116.              || (newsite->coord.y == newintstar.y 
  117.                  && newsite->coord.x < newintstar.x))) {
  118.         out_site(newsite);
  119.         lbnd = ELleftbnd(&(newsite->coord));
  120.         rbnd = ELright(lbnd);
  121.         bot = rightreg(lbnd);
  122.         e = bisect(bot, newsite);
  123.         bisector = HEcreate(e, le);
  124.         ELinsert(lbnd, bisector);
  125.         if ((p = intersect(lbnd, bisector)) != (struct Site *) NULL) {
  126.         PQdelete(lbnd);
  127.         PQinsert(lbnd, p, dist(p,newsite));
  128.         }
  129.         lbnd = bisector;
  130.         bisector = HEcreate(e, re);
  131.         ELinsert(lbnd, bisector);
  132.         if ((p = intersect(bisector, rbnd)) != (struct Site *) NULL) {
  133.         PQinsert(bisector, p, dist(p,newsite));    
  134.         }
  135.         newsite = (*nextsite)();    
  136.     } else if (!PQempty()) {
  137.     /* intersection is smallest */
  138.         lbnd = PQextractmin();
  139.         llbnd = ELleft(lbnd);
  140.         rbnd = ELright(lbnd);
  141.         rrbnd = ELright(rbnd);
  142.         bot = leftreg(lbnd);
  143.         top = rightreg(rbnd);
  144.         out_triple(bot, top, rightreg(lbnd));
  145.         v = lbnd->vertex;
  146.         makevertex(v);
  147.         v_endpoint(lbnd->ELedge,lbnd->ELpm,v);
  148.         v_endpoint(rbnd->ELedge,rbnd->ELpm,v);
  149.         ELdelete(lbnd); 
  150.         PQdelete(rbnd);
  151.         ELdelete(rbnd); 
  152.         pm = le;
  153.         if (bot->coord.y > top->coord.y) {    
  154.         temp = bot; 
  155.         bot = top; 
  156.         top = temp; 
  157.         pm = re;
  158.         }
  159.         e = bisect(bot, top);
  160.         bisector = HEcreate(e, pm);
  161.         ELinsert(llbnd, bisector);
  162.         v_endpoint(e, re-pm, v);
  163.         deref(v);
  164.         if((p = intersect(llbnd, bisector)) != (struct Site *) NULL) {
  165.         PQdelete(llbnd);
  166.         PQinsert(llbnd, p, dist(p,bot));
  167.         }
  168.         if((p = intersect(bisector, rrbnd)) != (struct Site *) NULL) 
  169.         PQinsert(bisector, p, dist(p,bot));
  170.     } else 
  171.         break;
  172.     }
  173.  
  174.     for(lbnd=ELright(ELleftend); lbnd != ELrightend; lbnd=ELright(lbnd)) {
  175.     e = lbnd->ELedge;
  176.     out_ep(e);
  177.         }
  178. }
  179.  
  180.  
  181.